//
// Created by francklinson on 2021/5/23.
//
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
        // 暴力
        sort(nums.begin(), nums.end());
        vector<int> ans;
        for (auto &querie : queries) {
            int x = querie[0]; // 用来XOR的x
            int y = querie[1]; // 上限
            int maxXor = -1;
            if (nums[0] > y) {
                ans.push_back(-1);
                continue;
            }
            for (int num : nums) {
                if (num > y) break;
                maxXor = max(maxXor, x ^ num);
            }
            ans.push_back(maxXor);
        }
        return ans;
        // 超时
    }
};
//TODO 字典树   不会
class Trie {
public:
    const int L = 30;

    Trie* children[2] = {};
    int min = INT_MAX;

    void insert(int val) {
        Trie* node = this;
        node->min = std::min(node->min, val);
        for (int i = L - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node->children[bit] == nullptr) {
                node->children[bit] = new Trie();
            }
            node = node->children[bit];
            node->min = std::min(node->min, val);
        }
    }

    int getMaxXorWithLimit(int val, int limit) {
        Trie* node = this;
        if (node->min > limit) {
            return -1;
        }
        int ans = 0;
        for (int i = L - 1; i >= 0; --i) {
            int bit = (val >> i) & 1;
            if (node->children[bit ^ 1] != nullptr && node->children[bit ^ 1]->min <= limit) {
                ans |= 1 << i;
                bit ^= 1;
            }
            node = node->children[bit];
        }
        return ans;
    }
};

class Solution2 {
public:
    vector<int> maximizeXor(vector<int> &nums, vector<vector<int>> &queries) {
        Trie* t = new Trie();
        for (int val : nums) {
            t->insert(val);
        }
        int numQ = queries.size();
        vector<int> ans(numQ);
        for (int i = 0; i < numQ; ++i) {
            ans[i] = t->getMaxXorWithLimit(queries[i][0], queries[i][1]);
        }
        return ans;
    }
};


int main() {
    vector<int> nums{0, 1, 2, 3, 4};
    vector<int> nums2{5, 2, 4, 6, 6, 3};
    vector<vector<int>> queries{{3, 1},
                                {1, 3},
                                {5, 6}};
    vector<vector<int>> queries2{{12, 4},
                                 {8,  1},
                                 {6,  3}};
    Solution2 sol;
    auto ans = sol.maximizeXor(nums, queries);
    auto ans2 = sol.maximizeXor(nums2, queries2);
    for (auto &x:ans) cout << x << endl;
    for (auto &x:ans2) cout << x << endl;
    return 0;
}